package com.model;

import java.awt.Color;
import java.awt.Container;
import java.awt.Graphics;
import java.awt.event.MouseAdapter;
import java.awt.event.MouseEvent;

import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;

import javax.swing.*;


import java.util.*;
import java.lang.Math;
import java.util.concurrent.*;
import java.util.concurrent.atomic.AtomicInteger;

public class Draw{
    public static void main(String[] args) {
        new DrawSee();
    }
}

class DrawSee extends JFrame {

    public int  boardWidth = 8;
	public Game game = new Game(boardWidth);

    public int offset = 60;
	public int geziWidth = 20;

    public Container conn;
    private Graphics jg;

    public DrawSee() {
        conn = this.getContentPane();
        setBounds(1500, 500, offset+geziWidth*(boardWidth+1)+40, offset+geziWidth*(boardWidth+1)+40+60);
        setVisible(true);
        conn.setBackground(new Color(255,255,255));
        setLayout(null);
        setResizable(false);
        this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

        Container conn = this.getContentPane();
        JButton btn1 = new JButton("pass");
        btn1.setBounds(10,offset+geziWidth*boardWidth+30,100,30);
        conn.add(btn1);

        btn1.addActionListener(new ActionListener() {
            public void actionPerformed(ActionEvent e) {
                game.placePiece(-1, -1, game.curColor);
                drawState(game.curState);
            }
        });



        try {
            Thread.sleep(500);
        } catch (Exception e) {
            e.printStackTrace();
        }



        jg =  this.getGraphics();
		clearDesk();
		drawState(game.curState);

        this.addMouseListener(new MouseAdapter() {


            public void mouseReleased(MouseEvent e) {

                int xm = e.getX(), ym = e.getY();

				float canvasX = xm - offset;
				float canvasY = ym - offset;

				int x = (int) Math.floor(canvasX / geziWidth);
				int y = (int) Math.floor(canvasY / geziWidth);

				if(x < 0 || x >= boardWidth || y < 0 || y >= boardWidth) {
					return;
				}

				if(game.curState.cellMap.containsKey(game.curState.xy2idx(x,y))) {
					return;
				}

				game.placePiece(x, y, game.curColor);

				drawState(game.curState);

            }

        });

    }

    public void clearDesk(){
		try {
            jg.setColor(new Color(255,255,255));
            jg.fillRect(0,0, 800, offset+geziWidth*(boardWidth+1)+40);
            jg.setColor(new Color(250,190,70));
            jg.fillRect(offset-geziWidth/2, offset-geziWidth/2, geziWidth*(boardWidth+1), geziWidth*(boardWidth+1));
			jg.setColor(Color.black);
            for(int i = 0; i <= boardWidth; i ++) {
                jg.drawLine(i * geziWidth+offset,offset,i * geziWidth+offset,offset+geziWidth * boardWidth);
                jg.drawLine(offset,offset+geziWidth * i,offset+geziWidth * boardWidth,offset+geziWidth * i);
			}

        } catch (Exception e) {
            e.printStackTrace();
        }
	}

	public void drawPiece(int x,int y,int color){
		try {
			if(color == 1) {
				jg.setColor(Color.black);
			} else {
				jg.setColor(Color.white);
			}
			jg.fillArc(offset+geziWidth*x,offset+geziWidth*y,geziWidth,geziWidth,0,360);
        } catch (Exception e) {
            e.printStackTrace();
        }
	}

    public void drawLastMove(int x,int y){
        try {
            jg.setColor(Color.green);
            jg.drawRect(offset+geziWidth*x,offset+geziWidth*y,geziWidth,geziWidth);
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    public void drawLegalMoves(int x,int y,int color){
        try {
            if(color == 1) {
                jg.setColor(new Color(50,50,50));
            } else {
                jg.setColor(new Color(200,200,200));
            }
            jg.drawArc(offset+geziWidth*x+geziWidth/4,offset+geziWidth*y+geziWidth/4,geziWidth/2,geziWidth/2,0,360);
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

	public void drawState(State state){
		try {
			clearDesk();
			HashMap<Integer, Integer> cellMap = state.cellMap;
			cellMap.forEach((idx, value)->{
				int xy[] = game.curState.idx2xy(idx);
				drawPiece(xy[0],xy[1],cellMap.get(idx));
			});

            state.legalMoves.forEach((idx, value)->{
                int xy[] = game.curState.idx2xy(idx);
                drawLegalMoves(xy[0],xy[1],-state.lastMove.color);
            });

            drawLastMove(game.curState.lastMove.x, game.curState.lastMove.y);
        } catch (Exception e) {
            e.printStackTrace();
        }

        this.drawInfo();
	}

    public void drawInfo(){
        try {
            jg.setColor(new Color(0,0,0));
            String white = "white:(" + game.curState.lastMove.x + "," + game.curState.lastMove.y+ ")";
			jg.drawString(white, 10, offset + geziWidth*(boardWidth+1));
            String rate = "rate: " + (float)game.node.Q/(float)game.node.N;
			jg.drawString(rate, 10, offset + geziWidth*(boardWidth+1) + 20);

            if(game.winColor!=0){
                String winColor = "winColor: " + game.winColor;
			    jg.drawString(winColor, 10+100, offset + geziWidth*(boardWidth+1));
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

}

class Game{
	public int curColor;
	public int boardWidth;
	public State curState;
    public Node node;
    public int winColor = 0;

    Game(int boardWidth) {
        this.curColor = 1;
        this.boardWidth = boardWidth;
        this.curState = new State(this.boardWidth, null);
        curState.cellMap.put(this.curState.xy2idx(3,3), -1);
        curState.cellMap.put(this.curState.xy2idx(4,4), -1);
        curState.cellMap.put(this.curState.xy2idx(4,3), 1);
        curState.cellMap.put(this.curState.xy2idx(3,4), 1);
        this.curState.lastMove = new Cell(4,4,-1,null,null,this.curState,this.curState.xy2idx(4,4));
        this.curState.updateLegalMoves();
        this.node = new Node(null,this.curState);
    }

    public void placePiece(int x, int y, int color){

        if(color==1){
            boolean success = this.curState.checkPiece(x,y,color);
            if(success){

                if(x == -1){
                    if(this.curState.lastMove.x == -1){
                        this.winColor = this.node.getWinColor(this.curState);
                        System.out.println("winner: " + this.winColor);
                        this.showResult();
                        return;
                    }
                }

                this.curState.placePiece(x,y,color);
                this.curColor = -this.curColor;

                //ai
                Node node = this.node.getChild(x,y);
                if(node==null){
                    node = new Node(null,this.curState);
                }

                int runTime = 2000;
                node.runTime = runTime;
                long startTime = System.currentTimeMillis();

                for(int i=0; i<runTime; i++){
                    node.runOnce();
                }

                long endTime = System.currentTimeMillis();
                System.out.println(runTime+"次耗时：" + (endTime-startTime)/1000.0+"秒");
                System.out.println("单次耗时：" + (float)(endTime-startTime)/runTime+"毫秒");

                Node bestChild = node.getMaxNChild();
                // Node bestChild = node.getMaxRateChild();
                if(bestChild!=null){

                    if(bestChild.state.lastMove.x == -1){
                        if(this.curState.lastMove.x == -1){
                            this.winColor = this.node.getWinColor(this.curState);
                            System.out.println("winner: " + this.winColor);
                            this.showResult();
                            return;
                        }
                    }

                    this.curState = bestChild.state;
                    this.curColor = -this.curColor;
                    this.node = bestChild;

                }

            }
        }

    }

    public void showResult(){
        String result;
        if(this.winColor==1){
            result = "黑胜";
        }else if(this.winColor==-1){
            result = "白胜";
        }else {
            result = "平局";
        }
        JOptionPane.showConfirmDialog (null, result, "结束", JOptionPane.DEFAULT_OPTION, JOptionPane.INFORMATION_MESSAGE);
    }

}

class Cell{

	public int x;
	public int y;
	public int color;
	public Cell head;
	public Cell next;
	public State state;
	public HashMap<Integer, Boolean> qi;
	public int idx;

	Cell(int x, int y, int color, Cell head, Cell next, State state, int idx) {
		this.x = x;
		this.y = y;
		this.color = color;
		this.head = head;
		this.next = next;
		this.state = state;
		this.qi = new HashMap<Integer, Boolean>();
		this.idx = idx;

		this.initQi();
	}

	void initQi(){
		int x = this.x;
		int y = this.y;
		if(y-1>=0){
			int idx = this.state.xy2idx(x,y-1);
			if(!this.state.cellMap.containsKey(idx)){
				this.qi.put(idx, true);
			}
		}
		if(y+1<this.state.boardWidth){
			int idx = this.state.xy2idx(x,y+1);
			if(!this.state.cellMap.containsKey(idx)){
				this.qi.put(idx, true);
			}
		}
		if(x-1>=0){
			int idx = this.state.xy2idx(x-1,y);
			if(!this.state.cellMap.containsKey(idx)){
				this.qi.put(idx, true);
			}
		}
		if(x+1<this.state.boardWidth){
			int idx = this.state.xy2idx(x+1,y);
			if(!this.state.cellMap.containsKey(idx)){
				this.qi.put(idx, true);
			}
		}

	}

	public boolean mergeBlock(Cell cell2){

		boolean merged = false;

		if(cell2.qi.containsKey(this.idx)){
            Cell cell = this;
            while(cell.next!=null){
                cell = cell.next;
            }
            cell.next = cell2;

            merged = true;
        }

//		for (Map.Entry<Integer, Boolean> entry : cell2.qi.entrySet()) {
//			int idx2 = entry.getKey();
//
//			if(idx2 == this.idx){
//				Cell cell = this;
//				while(cell.next!=null){
//					cell = cell.next;
//				}
//				cell.next = cell2;
//
//				merged = true;
//				break;
//			}
//		}

		if(merged){

			cell2.qi.remove(this.idx);
            cell2.qi.putAll(this.qi);

//			this.qi.forEach((idx, value2) -> {
//				cell2.qi.put(idx, true);
//			});

			this.qi = cell2.qi;
		}

		return merged;

	}

	public boolean deleteQi(Cell cell2){

		boolean deleted = false;

		int deleteIdx = 0;

		if(this.qi.containsKey(cell2.idx)){
            deleteIdx = cell2.idx;
            deleted = true;
        }
//		for (Map.Entry<Integer, Boolean> entry : this.qi.entrySet()) {
//			int idx = entry.getKey();
//			if(idx == cell2.idx){
//				deleteIdx = idx;
//				deleted = true;
//				break;
//			}
//		}
		if(deleted){
			this.qi.remove(deleteIdx);
		}

		return deleted;
	}

	public void addQi(Cell cell3){

		Cell cell2 = cell3;
		do{
			Cell cell = this;
			do{
				if(cell.idx-this.state.boardWidth == cell2.idx || cell.idx+this.state.boardWidth == cell2.idx || cell.x>0&&cell.idx-1 == cell2.idx || cell.x<this.state.boardWidth-1&&cell.idx+1 == cell2.idx){
					this.qi.put(cell2.idx, true);
					break;
				}
				cell = cell.next;
			}while(cell!=null);
			cell2 = cell2.next;
		}while(cell2!=null);

	}

	public int getQiCount(){
		return this.qi.size();
	}

	public int getCount(){

		int count = 1;
		Cell cell = this;
		while(cell.next!=null){
			count ++;
			cell = cell.next;
		}
		return count;
	}

}

class State{
	public HashMap<Integer, Integer>  cellMap;

	public int boardWidth;
	public Cell lastMove;
	public int result;
	public HashMap<Integer, ArrayList<Integer>> legalMoves;

	State(int boardWidth, Cell lastMove) {
        this.cellMap = new HashMap<Integer, Integer>();
        this.legalMoves = new HashMap<Integer, ArrayList<Integer>>();
        this.boardWidth = boardWidth;
        this.lastMove = lastMove;

    }

    public int xy2idx(int x, int y){
        return y*this.boardWidth+x;
    }

    public int[] idx2xy(int idx){
        int x = idx%this.boardWidth;
        int y = (idx-x)/this.boardWidth;
        return new int[]{x,y};
    }

    public State clone(){
        State state = new State(this.boardWidth,this.lastMove);

        HashMap<Integer, Integer> cellMap = new HashMap<Integer, Integer>();
		this.cellMap.forEach((key, value) -> {
            cellMap.put(key, value);
        });
        state.cellMap = cellMap;

        HashMap<Integer, ArrayList<Integer>> legalMoves = new HashMap<Integer, ArrayList<Integer>>();
        this.legalMoves.forEach((key, value) -> {
            legalMoves.put(key, value);
        });
        state.legalMoves = legalMoves;

        return state;

    }

    public void updateLegalMoves(){
	    this.legalMoves.clear();
	    int color = -this.lastMove.color;

        for (int x = 0; x < this.boardWidth; x++) {
            for (int y = 0; y < this.boardWidth; y++) {
                int idx = this.xy2idx(x,y);
                if(this.cellMap.containsKey(idx)){
                    continue;
                }

                //up
                if(y-1>=0){
                    int idxu = this.xy2idx(x,y-1);
                    int colorU = this.cellMap.getOrDefault(idxu,0);
                    if(colorU == -color){
                        ArrayList reversList = new ArrayList<Integer>();
                        reversList.add(idxu);
                        for (int yu = y-2; yu >= 0; yu--) {
                            int idxu0 = this.xy2idx(x,yu);
                            int colorU0 = this.cellMap.getOrDefault(idxu0,0);
                            if(colorU0 == color){
                                if(!this.legalMoves.containsKey(idx)){
                                    this.legalMoves.put(idx, reversList);
                                }else {
                                    this.legalMoves.get(idx).addAll(reversList);
                                }
                                break;
                            }else if(colorU0 == -color){
                                reversList.add(idxu0);
                            }else {
                                break;
                            }
                        }
                    }
                }


                //down
                if(y+1<this.boardWidth){
                    int idxd = this.xy2idx(x,y+1);
                    int colorD = this.cellMap.getOrDefault(idxd,0);
                    if(colorD == -color){
                        ArrayList reversList = new ArrayList<Integer>();
                        reversList.add(idxd);
                        for (int yu = y+2; yu < this.boardWidth; yu++) {
                            int idxu0 = this.xy2idx(x,yu);
                            int colorU0 = this.cellMap.getOrDefault(idxu0,0);
                            if(colorU0 == color){
                                if(!this.legalMoves.containsKey(idx)){
                                    this.legalMoves.put(idx, reversList);
                                }else {
                                    this.legalMoves.get(idx).addAll(reversList);
                                }
                                break;
                            }else if(colorU0 == -color){
                                reversList.add(idxu0);
                            }else {
                                break;
                            }
                        }
                    }
                }

                //left

                if(x-1>=0){
                    int idxl = this.xy2idx(x-1,y);
                    int colorL = this.cellMap.getOrDefault(idxl,0);
                    if(colorL == -color){
                        ArrayList reversList = new ArrayList<Integer>();
                        reversList.add(idxl);
                        for (int xu = x-2; xu >= 0; xu--) {
                            int idxu0 = this.xy2idx(xu,y);
                            int colorU0 = this.cellMap.getOrDefault(idxu0,0);
                            if(colorU0 == color){
                                if(!this.legalMoves.containsKey(idx)){
                                    this.legalMoves.put(idx, reversList);
                                }else {
                                    this.legalMoves.get(idx).addAll(reversList);
                                }
                                break;
                            }else if(colorU0 == -color){
                                reversList.add(idxu0);
                            }else {
                                break;
                            }
                        }
                    }
                }

                //right
                if(x+1<this.boardWidth){
                    int idxr = this.xy2idx(x+1,y);
                    int colorR = this.cellMap.getOrDefault(idxr,0);
                    if(colorR == -color){
                        ArrayList reversList = new ArrayList<Integer>();
                        reversList.add(idxr);
                        for (int xu = x+2; xu < this.boardWidth; xu++) {
                            int idxu0 = this.xy2idx(xu,y);
                            int colorU0 = this.cellMap.getOrDefault(idxu0,0);
                            if(colorU0 == color){
                                if(!this.legalMoves.containsKey(idx)){
                                    this.legalMoves.put(idx, reversList);
                                }else {
                                    this.legalMoves.get(idx).addAll(reversList);
                                }
                                break;
                            }else if(colorU0 == -color){
                                reversList.add(idxu0);
                            }else {
                                break;
                            }
                        }
                    }
                }

                //up left
                if(x-1>=0&&y-1>=0){
                    int idxul = this.xy2idx(x-1,y-1);
                    int colorUL = this.cellMap.getOrDefault(idxul,0);
                    if(colorUL == -color){
                        ArrayList reversList = new ArrayList<Integer>();
                        reversList.add(idxul);
                        for (int xu = x-2, yu = y-2; xu >= 0&&yu >= 0; xu--,yu--) {
                            int idxu0 = this.xy2idx(xu,yu);
                            int colorU0 = this.cellMap.getOrDefault(idxu0,0);
                            if(colorU0 == color){
                                if(!this.legalMoves.containsKey(idx)){
                                    this.legalMoves.put(idx, reversList);
                                }else {
                                    this.legalMoves.get(idx).addAll(reversList);
                                }
                                break;
                            }else if(colorU0 == -color){
                                reversList.add(idxu0);
                            }else {
                                break;
                            }
                        }
                    }
                }

                //up right
                if(x+1<this.boardWidth&&y-1>=0){
                    int idxur = this.xy2idx(x+1,y-1);
                    int colorUR = this.cellMap.getOrDefault(idxur,0);
                    if(colorUR == -color){
                        ArrayList reversList = new ArrayList<Integer>();
                        reversList.add(idxur);
                        for (int xu = x+2, yu = y-2; xu < this.boardWidth&&yu >= 0; xu++,yu--) {
                            int idxu0 = this.xy2idx(xu,yu);
                            int colorU0 = this.cellMap.getOrDefault(idxu0,0);
                            if(colorU0 == color){
                                if(!this.legalMoves.containsKey(idx)){
                                    this.legalMoves.put(idx, reversList);
                                }else {
                                    this.legalMoves.get(idx).addAll(reversList);
                                }
                                break;
                            }else if(colorU0 == -color){
                                reversList.add(idxu0);
                            }else {
                                break;
                            }
                        }
                    }
                }

                //down left
                if(x-1>=0&&y+1<this.boardWidth){
                    int idxdl = this.xy2idx(x-1,y+1);
                    int colorDL = this.cellMap.getOrDefault(idxdl,0);
                    if(colorDL == -color){
                        ArrayList reversList = new ArrayList<Integer>();
                        reversList.add(idxdl);
                        for (int xu = x-2, yu = y+2; xu >= 0&&yu < this.boardWidth; xu--,yu++) {
                            int idxu0 = this.xy2idx(xu,yu);
                            int colorU0 = this.cellMap.getOrDefault(idxu0,0);
                            if(colorU0 == color){
                                if(!this.legalMoves.containsKey(idx)){
                                    this.legalMoves.put(idx, reversList);
                                }else {
                                    this.legalMoves.get(idx).addAll(reversList);
                                }
                                break;
                            }else if(colorU0 == -color){
                                reversList.add(idxu0);
                            }else {
                                break;
                            }
                        }
                    }
                }


                //down right
                if(x+1<this.boardWidth&&y+1<this.boardWidth){
                    int idxdr = this.xy2idx(x+1,y+1);
                    int colorDR = this.cellMap.getOrDefault(idxdr,0);
                    if(colorDR == -color){
                        ArrayList reversList = new ArrayList<Integer>();
                        reversList.add(idxdr);
                        for (int xu = x+2, yu = y+2; xu < this.boardWidth&&yu < this.boardWidth; xu++,yu++) {
                            int idxu0 = this.xy2idx(xu,yu);
                            int colorU0 = this.cellMap.getOrDefault(idxu0,0);
                            if(colorU0 == color){
                                if(!this.legalMoves.containsKey(idx)){
                                    this.legalMoves.put(idx, reversList);
                                }else {
                                    this.legalMoves.get(idx).addAll(reversList);
                                }
                                break;
                            }else if(colorU0 == -color){
                                reversList.add(idxu0);
                            }else {
                                break;
                            }
                        }
                    }
                }

            }
        }
    }

    public boolean checkPiece(int x,int y,int color){
	    if(x==-1&&y==-1){
	        return true;
        }
        return this.legalMoves.containsKey(this.xy2idx(x,y));
    }

    public void placePiece(int x,int y,int color){

        int idx = this.xy2idx(x,y);
        this.lastMove = new Cell(x,y,color,null,null,this,idx);

        if(x!=-1){
            this.cellMap.put(idx,color);
            ArrayList<Integer> reversIdxs = this.legalMoves.get(idx);
            for (int i = 0; i < reversIdxs.size(); i++) {
                int idx0 = reversIdxs.get(i);
                this.cellMap.put(idx0,color);
            }
        }

    }

}

class Node implements Callable<Integer> {
    public Node father;
    public float ucb;
    public int Q;
    public int N;
    public ArrayList<Node> children;
    public Node maxUCBChild;
    public State state;
    public boolean end;
    public int winColor = 0;
    public int runTime = 3000;

    Node(Node father, State state){
        this.father = father;
        this.ucb = -Float.MAX_VALUE;
        this.Q = 0;
        this.N = 0;
        this.children = new ArrayList<Node>();
        this.maxUCBChild = null;
        this.state = state;
        this.end = false;
    }

    public Node clone(){
        Node node = new Node(this.father, this.state.clone());
        node.ucb = this.ucb;
        node.ucb = this.ucb;
        node.Q = this.Q;
        node.N = this.N;
        node.maxUCBChild = this.maxUCBChild;
        node.end = this.end;
        node.runTime = this.runTime;
        node.children = new ArrayList<Node>();
        for (Node child : this.children) {
            node.children.add(child.clone());
        }
        return node;
    }

    public void runOnce(){
        Node selectedNode = this;

        while(selectedNode.children.size()>0){
            selectedNode = selectedNode.setMaxUCBChild();
        }

        if(selectedNode.N>0){
            if(selectedNode.end){
                this.backpropagation(selectedNode.winColor, selectedNode);
                return;
            }
            selectedNode.createChildren();
            selectedNode = selectedNode.children.get(0);
        }

        if(selectedNode.end){
            if(selectedNode.winColor==0){
                selectedNode.winColor = this.getWinColor(selectedNode.state);
            }
            this.backpropagation(selectedNode.winColor, selectedNode);
            return;
        }

        int winColor = selectedNode.simulate();
        Node node = selectedNode;

        this.backpropagation(winColor, node);

    }

    public void runSomeTimes(int times){
        for (int i = 0; i < times; i++) {
            this.runOnce();
        }
    }

    public void backpropagation(int winColor, Node node){
        do{
            node.updateQN(winColor);
            node = node.father;
        }while(node!=null);
    }

    public void updateQN(int winColor){
        this.N++;
        if(winColor==this.state.lastMove.color){
            this.Q++;
        }else {
            this.Q--;
        }
    }

    public Node setMaxUCBChild(){
        float max = -Float.MAX_VALUE;
        List<Node> noVisitedNodeList = new ArrayList<>();
        for(int idx=0; idx<this.children.size(); idx++){
            Node item = this.children.get(idx);
            float ucb = item.updateUCB();
            if(ucb>max){
                max = ucb;
                this.maxUCBChild = item;

                if(item.N == 0){
                    noVisitedNodeList.add(item);
                }
            }
        }

        int noVisitedSize = noVisitedNodeList.size();
        if(noVisitedSize>1){
            int idx = getRandomInt(noVisitedSize);
            this.maxUCBChild = noVisitedNodeList.get(idx);
        }
        return this.maxUCBChild;
    }

    public Node getMaxNChild(){
        int max = -Integer.MAX_VALUE;
        Node best=null;
        for(int idx=0; idx<this.children.size(); idx++){
            int N = this.children.get(idx).N;
            if(N>max){
                max = N;
                best = this.children.get(idx);
            }else if(N==max){
                if(this.children.get(idx).Q>best.Q){
                    max = N;
                    best = this.children.get(idx);
                }
            }
        }
        return best;
    }

    public Node getMaxRateChild(){
        float max = -Float.MAX_VALUE;
        Node best=null;
        for(int idx=0; idx<this.children.size(); idx++){
            float rate = (float)this.children.get(idx).Q/(float)this.children.get(idx).N;
            if(rate>max){
                max = rate;
                best = this.children.get(idx);
            }
        }
        return best;
    }

    public void createChildren(){
        int color = -this.state.lastMove.color;
        this.state.updateLegalMoves();
        this.state.legalMoves.forEach((idx, value) -> {
            State state = this.state.clone();
            int[] xy = this.state.idx2xy(idx);

            state.placePiece(xy[0], xy[1], color);
            Node node = new Node(this,state);
            this.children.add(node);
        });

        if(this.state.legalMoves.size()==0){
            int idx = this.state.xy2idx(-1,-1);
            State state1 = this.state.clone();
            Cell cell = new Cell(-1, -1, color, null, null, state1, idx);
            state1.lastMove = cell;
            Node node = new Node(this,state1);
            this.children.add(node);

            if(this.state.lastMove.x==-1){
                node.end = true;
            }
        }

    }

    public int simulate(){
        boolean end = false;
        State state = this.state.clone();
        int lastX = state.lastMove.x;
        do{
            int color = -state.lastMove.color;
            ArrayList<Integer> allMove = new ArrayList<>();

            state.updateLegalMoves();
            state.legalMoves.forEach((idx, value) -> {
                allMove.add(idx);
            });

            if(allMove.size()==0){
                state.lastMove = new Cell(-1,-1,color,null,null,state,state.xy2idx(-1,-1));
                if(lastX == -1){
                    end = true;
                }
                lastX = -1;
            }else{
                int selectIdx = this.getRandomInt(allMove.size());
                int selectedIdx = allMove.get(selectIdx);
                int[] xy = this.state.idx2xy(selectedIdx);
                state.placePiece(xy[0], xy[1], color);
                lastX = xy[0];
            }

        }while(!end);

        int winColor = this.getWinColor(state);

        this.winColor = winColor;
        return winColor;

    }

    public int getWinColor(State state){
        AtomicInteger black = new AtomicInteger();
        AtomicInteger white = new AtomicInteger();

        state.cellMap.forEach((idx, color) -> {
            if(color==1){
                black.getAndIncrement();
            }else if(color==-1){
                white.getAndIncrement();
            }
        });

        if(black.get() > white.get()){
            return 1;
        }else if(black.get() < white.get()){
            return -1;
        }else {
            return 0;
        }
    }

    public int getRandomInt(int max) {
        return (int)Math.floor(Math.random() * (float)max);
    }

    public float updateUCB(){
        if(this.N==0){
            return Float.MAX_VALUE;
        }
        this.ucb = (float) ((float)this.Q/(float)this.N + Math.sqrt(2.0*Math.log((float)this.father.N)/(float)this.N));
        return this.ucb;
    }

    public Node getChild(int x,int y){
        for(int idx=0; idx<this.children.size(); idx++){
            Cell lastMove = this.children.get(idx).state.lastMove;
            if(lastMove.x==x&&lastMove.y==y){
                return this.children.get(idx);
            }
        }
        return null;
    }

    @Override
    public Integer call(){
        this.runSomeTimes(this.runTime);
        return 1;
    }
}


